/* 费用流 算法应用
* 1.基础概念
    费用流即最小/大费用最大流（即最大可行流中的最小/大费用）
    费用流：最大流时每条边上的可行流×该边上的费用

* 2.求解算法
    将 EK 算法中的 bfs 改为 spfa，spfa 用来求解源点 S 到 T 的最短/长路（即 S 到 T 上的最小路径费用和）
    在求最短/长路的同时找到一条增广路径，然后增加这部分的费用，直到找不到增广路径为止

    spfa不可处理负权回路，如果图中有负权回路，需要消圈

    只要当前沿着最短路径增广，则一定能求得最小费用流

* 本题:
    最大流
    边只能走一次:边的容量为1
    点只能走一次:拆点，将图中的每一个点拆为入点和出点, 入点到出点的容量为1。

    一类边：从入点向出点连价值 costi,j的边。
    二类边：对于每一个可走的边，连价值为0的边。
    三类边：从源点 S 像第一行的点连价值为 0 的边。
    四类边：从最后一行向汇点连价值为 0 的边。

    规则一：所有边容量为1。
    规则二：一类边和四类边容量改为INF。
    规则三：一类边，二类边和四类边容量改为INF。
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1210, M = 4010, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], c[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int id[40][40], cost[40][40];

void AddEdge(int a, int b, int cc, int ww)
{
    e[idx] = b, c[idx]=cc, w[idx]=ww, ne[idx]=h[a], h[a]=idx++;
    e[idx] = a, c[idx]=0, w[idx]=-ww, ne[idx]=h[b], h[b]=idx++;
}

bool spfa() 
{
    memset(d, -0x3f, sizeof d); //本题求解最大流
    memset(incf, 0, sizeof incf);

    int hh=0, tt=0;
    q[tt++]=S, d[S]=0, incf[S]=INF;

    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N) hh=0;
        st[u]=false;

        for(int i=h[u]; ~i; i=ne[i])
        {
            int v=e[i];
            if(c[i] && d[v] < d[u]+w[i])
            {
                d[v] = d[u]+w[i];
                incf[v] = min(incf[u], c[i]);
                pre[v] = i;
                if(!st[v])
                {
                    st[v] = true; //如果之前没有访问过，则置已访问，除非有多条边可指向v，即在队列中有多次入队
                    q[tt++] = v;
                    if(tt==N) tt=0;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK() 
{
    int cost=0;
    while(spfa())
    {
        cost+=incf[T]*d[T]; //当前流的最值流
        for(int i=T; i!=S; i=e[pre[i]^1])
        {
            c[pre[i]] -= incf[T]; c[pre[i]^1] += incf[T]; 
        }

    }
    return cost;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif

    int cnt = 0;
    cin >> m >> n;

    S=++cnt, T=++cnt;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i+m-1; j++)
        {
            cin >> cost[i][j];
            id[i][j]=++cnt;
        }

    //规则一 所有路径的点和边都不能相交，即所有点和所有边都只能走一次
    memset(h, -1, sizeof h); 
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i+m-1; j++)
        {
            AddEdge(id[i][j]<<1, id[i][j]<<1|1, 1, cost[i][j]); //从每个点的入点向出点连一条边，容量是 1，费用是当前点的权值
            if(i==1) AddEdge(S, id[i][j]<<1, 1, 0); //从源点向所有顶点连一条边，容量是 1，费用是 0
            if(i<n)
            {
                AddEdge(id[i][j]<<1|1, id[i+1][j]<<1, 1, 0); //从当前点向正下方的点连一条边，容量是 1，费用是 0
                AddEdge(id[i][j]<<1|1, id[i+1][j+1]<<1, 1, 0); //从当前点向右下方的点连一条边，容量是 1，费用是 0
            } 
            if(i==n)
                AddEdge(id[i][j]<<1|1, T, 1, 0); //从所有底点向汇点连一条边，容量是 1，费用是 0
        }

    printf("%d\n", EK()); 

    //规则二 所有路径的边都不能相交，即所有边只能走一次，所有点可以走无数次
    memset(h, -1, sizeof h); idx=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i+m-1; j++)
        {
            AddEdge(id[i][j]<<1, id[i][j]<<1|1, INF, cost[i][j]); //从每个点的入点向出点连一条边，容量是 INF，费用是当前点的权值
            if(i==1) AddEdge(S, id[i][j]<<1, 1, 0); //从源点向所有顶点连一条边，容量是 1，费用是 0
            if(i<n)
            {
                AddEdge(id[i][j]<<1|1, id[i+1][j]<<1, 1, 0); //从当前点向正下方的点连一条边，容量是 1，费用是 0
                AddEdge(id[i][j]<<1|1, id[i+1][j+1]<<1, 1, 0); //从当前点向右下方的点连一条边，容量是 1，费用是 0
            } 
            if(i==n)
                AddEdge(id[i][j]<<1|1, T, INF, 0); //从所有底点向汇点连一条边，容量是 INF，费用是 0
        }

    printf("%d\n", EK()); 

    //规则三 所有路径的点和边都可以相交，即所有点和所有边都可以走无数次
    memset(h, -1, sizeof h); idx=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i+m-1; j++)
        {
            AddEdge(id[i][j]<<1, id[i][j]<<1|1, INF, cost[i][j]);
            if(i==1) AddEdge(S, id[i][j]<<1, 1, 0); 
            if(i<n)
            {
                AddEdge(id[i][j]<<1|1, id[i+1][j]<<1, INF, 0); 
                AddEdge(id[i][j]<<1|1, id[i+1][j+1]<<1, INF, 0); 
            } 
            if(i==n)
                AddEdge(id[i][j]<<1|1, T, INF, 0); 
        }

    printf("%d\n", EK()); 
    return 0;
}